﻿//给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。
//当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。
//
//输入：s = "abcbdd"
//输出：true
//解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。
//
//输入：s = "bcbddxy"
//输出：false
//解释：s 没办法被分割成 3 个回文子字符串。
//
//提示：
//	3 <= s.length <= 2000
//	s​​​​​​ 只包含小写英文字母。

class Solution {
public:
    bool checkPartitioning(string s) {
        // 1.⽤ dp 把所有的⼦串是否是回⽂预处理⼀下

        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        for (int i = n - 1; i >= 0; i--)
            for (int j = i; j < n; j++)
                if (s[i] == s[j])
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;

        // 2.枚举所有的第⼆个字符串的起始位置以及结束位置
        for (int i = 1; i < n - 1; i++)
            for (int j = i; j < n - 1; j++)
                if (dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1])
                    return true;
        return false;
    }
};